Calculs d'inverses - Corrigé

Énoncé

Déterminer un inverse :

1. de \(8\) modulo \(15\)  ;

2. de \(11\) modulo \(19\)  ;

3. de \(23\) modulo \(32\) .

Solution

a. On applique l'algorithme d'Euclide pour \(15\) et \(8\) :

\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r\\ \hline 15&8&1&7\\ \hline 8&7&1&1\\ \hline 7&1&7&0\\ \hline \end{array} \begin{array}{ll}\ & \\ \times (-1)& \text{suppression du reste } 7\\ \times 1& \text{conservation du PGCD}\\ & \end{array}\end{align*}\)   

En additionnant les lignes après avoir éliminé les restes intermédiaires, on obtient : \(\begin{align*}15 \times (-1)+8 \times 1=8 \times 1 \times (-1)+1& \ \ \Longleftrightarrow \ \ 15 \times (-1)+8 \times 2=1\end{align*}\) .
On a donc  \(8 \times 2 \equiv 1 \ [15]\) , donc  \(2\)  est un inverse de \(8\)  modulo  \(15\) .

Remarque  

On pouvait remarquer très rapidement que  \(8 \times 2 \equiv 16 \equiv 1 \ [15]\)  sans passer par l'algorithme d'Euclide !

b. On applique l'algorithme d'Euclide pour \(19\) et \(11\) :

\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r\\ \hline 19&11&1&8\\ \hline 11&8&1&3\\ \hline 8&3&2&2 \\ \hline 3&2&1&1 \\ \hline 2&1&2&0 \\ \hline \end{array} \begin{array}{ll}\ & \\ \times (-4) & \text{suppression du reste } 8 \\ \times 3 & \text{suppression du reste } 3 \\ \times (-1)& \text{suppression du reste } 2\\ \times 1& \text{conservation du PGCD}\\ & \end{array}\end{align*}\)   

En additionnant les lignes après avoir éliminé les restes intermédiaires, on obtient :  \(\begin{align*}19 \times (-4)+11 \times 3=11 \times 1 \times (-4)+1& \ \ \Longleftrightarrow \ \ 19 \times (-4)+11 \times 7=1\end{align*}\) .
On a donc  \(11 \times 7 \equiv 1 \ [19]\) , donc  \(7\)  est un inverse de \(11\)  modulo  \(19\) .

c. On applique l'algorithme d'Euclide pour \(32\) et \(23\) :

\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r\\ \hline 32&23&1&9\\ \hline 23&9&2&5\\ \hline 9&5&1&4 \\ \hline 5&4&1&1 \\ \hline 4&1&4&0 \\ \hline \end{array} \begin{array}{ll}\ & \\ \times (-5) & \text{suppression du reste } 9 \\ \times 2 & \text{suppression du reste } 5 \\ \times (-1)& \text{suppression du reste } 4\\ \times 1& \text{conservation du PGCD}\\ & \end{array}\end{align*}\)   

En additionnant les lignes après avoir éliminé les restes intermédiaires, on obtient :  \(\begin{align*}32 \times (-5)+23 \times 2=23 \times 1 \times (-5)+1& \ \ \Longleftrightarrow \ \ 32 \times (-5)+23 \times 7=1\end{align*}\) .
On a donc  \(23 \times 7 \equiv 1 \ [32]\) , donc  \(7\)  est un inverse de \(23\)  modulo  \(32\) .